原帖地址：[http://blog.leanote.com/post/dawnmagnet/bb6f3d567c46](http://blog.
leanote.com/post/dawnmagnet/bb6f3d567c46)
# 题目
![title](https://leanote.com/api/file/getImage?fileId=608b5493ab644155130179f
0)
# 思路分析
对于这种可以简单操作的题目，我的建议是在学习的时候一定要参透最难的做法，在真
正发挥的时候就怎么熟练怎么来。因为最难的做法是很难想到的，而我们要训练的就是
解决问题的能力。如果我们止步于简单的做法，我们的进步就非常缓慢了。
简单的做法非常简单，统计即可，时间和空间都是O(n)，就相当于拿一个哈希表遍历统
计一下即可。
那么这种写法实在是太简单了，我们就来参透一下困难的做法。也就是满足题目中的条
件所言，不使用额外空间（即使用O(1)空间复杂度）。那么显而易见，我们必须使用有
限的，固定的几个变量来存储之前遍历所有数字的状态。我们最理想的设想是，在我们
对这些数字进行运算之后，那个出现一次的数字自己出现了，也就是被过滤出来了，而
出现三次 就自动清零了。
我们先从简单的题目开始入手。将题目中的三次改成两次。那么题目就变成了[136. 
只出现一次的数字](https://leetcode-cn.com/problems/single-number/)
对于这种题目，我们不能谈论一个数字如何表示，我们要讨论它的二进制位如何表示。
因为统计一个二进制位，最后就可以还原出这个数字。
我们要设置一个状态，即一个位在有输入之前是0，输入一次之后变成1，输入两次变成
另一个状态（称为状态m)，输入三次又变成0。只有这样才能用这个状态来表示之前出现
过的所有数字的叠加。
这样我们就得到了一张推理表
|状态|数字|下一状态|
--|
0|1|1
1|1|m
m|1|0
0|0|0
1|0|1
m|0|m
我们知道计算机没法表示m这个状态，只能使用二进制位来表示，而表示三个状态所需要
的最小位数是2，所以我们扩展一下
0->00 1->01 m->11
那么上表就变成了
|状态|数字|下一状态(左a右b)|
--|
00|1|01
01|1|11
11|1|00
00|0|00
01|0|01
11|0|11
所以就相当于说，我们对于每一个原数字中的二进制位，我们都使用两个二进制位来表
示它的状态。所以我们可以分别将这两个二进制位放到两个int类型的数字里面，便于进
行比较和变化操作。
根据对二进制的理解，可以推出如下表达式
$$
a_{next}=b\&(a\oplus num) \\
b_{next} = (a \oplus b) | (b \oplus num)